from typing import List


class Solution:
    """
    暴力法：遍历整个二维数组
    """

    @staticmethod
    def search_matrix(matrix: List[List[int]], target: int) -> bool:
        return [True for num in matrix for j in num if j == target] != []


class Solution2:
    """
    二分法：对行坐标和列坐标分别使用二分法查找，最终判断坐标的值是否等于target值
    """
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row, col = len(matrix), len(matrix[0])
        # 初始化坐标
        x = y = 0
        # 固定列下标为最大列数，二分查找行下标
        up, down = 0, row - 1
        while up <= down:
            mid = up + (down - up) // 2
            # 列坐标始终固定，移动行下标
            if target <= matrix[mid][col - 1]:
                x = mid
                down = mid - 1
            else:
                up = mid + 1

        # 找到行下标后，二分查找列下标
        left, right = 0, col - 1
        while left <= right:
            mid = left + (right - left) // 2
            # 行下标固定为x，找列下标
            if target <= matrix[x][mid]:
                y = mid
                right = mid - 1
            else:
                left = mid + 1
        # 判断坐标(x,y)是否等于目标值
        return matrix[x][y] == target
